#include <bits/stdc++.h>

using namespace std;

// 好子集的数目
// 给你一个整数数组 nums，好子集的定义如下：
// nums的某个子集，所有元素的乘积可以表示为一个或多个互不相同质数的乘积
// 比如nums = [1, 2, 3, 4]
// [2, 3]，[1, 2, 3]，[1, 3] 是好子集
// 乘积分别为6=2*3，6=2*3，3=3
// [1, 4]和[4]不是好子集，因为乘积分别为4=2*2和4=2*2
// 请你返回nums中不同的好子集的数目对10^9+7取余的结果
// 如果两个子集删除的下标不同，那么它们被视为不同的子集
// 测试链接 : https://leetcode.cn/problems/the-number-of-good-subsets/

class Solution 
{
public:
	static const int MAXV = 30;
	static const int LIMIT = (1 << 10);
	static const int MOD = 1000000007;

	// 打个表来加速判断
	// 如果一个数字拥有某一种质数因子不只1个
	// 那么认为这个数字无效，状态全是0，0b0000000000
	// 如果一个数字拥有任何一种质数因子都不超过1个
	// 那么认为这个数字有效，用位信息表示这个数字拥有质数因子的状态
	// 比如12，拥有2这种质数因子不只1个，所以无效，用0b0000000000表示
	// 比如14，拥有2这种质数因子不超过1个，拥有7这种质数因子不超过1个，有效
	// 从高位到低位依次表示：...13 11 7 5 3 2
	// 所以用0b0000001001表示14拥有质数因子的状态
	// 质数: 29 23 19 17 13 11 7 5 3 2
	// 位置: 9 8 7 6 5 4 3 2 1 0
	static constexpr int own[31] = { 
            0b0000000000, // 0 不是质数
			0b0000000000, // 1 不是质数
			0b0000000001, // 2 是质数
			0b0000000010, // 3 是质数
			0b0000000000, // 4 需要多个相同的质数相乘
			0b0000000100, // 5 是质数
			0b0000000011, // 6 = 2 * 3
			0b0000001000, // 7 是质数
			0b0000000000, // 8 需要多个相同的质数相乘
			0b0000000000, // 9 需要多个相同的质数相乘
			0b0000000101, // 10 = 2 * 5
			0b0000010000, // 11 是质数
			0b0000000000, // 12 需要多个相同的质数相乘
			0b0000100000, // 13 是质数
			0b0000001001, // 14 = 2 * 7
			0b0000000110, // 15 = 3 * 5
			0b0000000000, // 16 需要多个相同的质数相乘
			0b0001000000, // 17 是质数
			0b0000000000, // 18 需要多个相同的质数相乘
			0b0010000000, // 19 是质数
			0b0000000000, // 20 需要多个相同的质数相乘
			0b0000001010, // 21 = 3 * 7
			0b0000010001, // 22 = 2 * 11
			0b0100000000, // 23 是质数
			0b0000000000, // 24 需要多个相同的质数相乘
			0b0000000000, // 25 需要多个相同的质数相乘
			0b0000100001, // 26 = 2 * 13
			0b0000000000, // 27 需要多个相同的质数相乘
			0b0000000000, // 28 需要多个相同的质数相乘
			0b1000000000, // 29 是质数
			0b0000000111  // 30 = 2 * 3 * 5
	};

    // 记忆化搜索
    int numberOfGoodSubsets1(vector<int>& nums) 
    {
        // 1 ~ 30
        int cnt[MAXV + 1];
        memset(cnt, 0, sizeof cnt);
        // 统计 num 的出现次数
        for(int num : nums) ++cnt[num];
        vector<vector<int>> dp(MAXV + 1, vector<int>(LIMIT, -1));
        int ans = 0;
        // 要将 nums 中的数划分形成好子集 s 的状态
        for(int s = 1; s < LIMIT; ++s)
        {
            ans = (ans + f1(MAXV, s, cnt, dp)) % MOD;
        }
        return ans;
    }

    // 1....i范围的数字，每种数字cnt[i]个
	// 最终相乘的结果一定要让质因子的状态为s，且每种质因子只能有1个
	// 请问子集的数量是多少
	// s每一位代表的质因子如下
	// 质数: 29 23 19 17 13 11 7 5 3 2
	// 位置: 9 8 7 6 5 4 3 2 1 0
    int f1(int i, int s, int* cnt, vector<vector<int>>& dp)
    {
        if(dp[i][s] != -1) return dp[i][s];
        int ans = 0;
        if(i == 1) // 只能选 1 这个数字了
        {
            // 只有当 s 等于 0，即不再需要任何的质数了
            // 此时才能累计答案
            if(s == 0)
            {
                ans = 1;
                for(int j = 0; j < cnt[1]; ++j)
                {
                    ans = (ans << 1) % MOD;
                }
            }
        }
        else
        {
            // 不要 i 这个数字
            ans = f1(i - 1, s, cnt, dp);
            // 如果 i 不是质数，则 cur 等于 0
            // 如果 i 是质数，则 cur 表示 i 有哪些质数组成
            int cur = own[i];
            // times 是数字 i 的出现次数
            int times = cnt[i];
            // s   : 10101
            // cur : 10100
            // s & cur : 10100
            // (s & cur) == cur 表示 i 中的所有质
            // 因子是 s 想要的，才能选择 i 这个数字
            if(cur != 0 && times != 0 && (s & cur) == cur)
            {
                // 能要 i 这个数字
                ans = (ans + (long)f1(i - 1, s ^ cur, cnt, dp) * times) % MOD;
            }
        }
        dp[i][s] = ans;
        return ans;
    }

    // 空间压缩优化
    int cnt[MAXV + 1];
    int dp[LIMIT];

    int numberOfGoodSubsets2(vector<int>& nums) 
    {
        // 统计 num 的出现次数
        for(int num : nums) ++cnt[num];
        // s 的状态为 0，即不再需要任何的质数了
        dp[0] = 1;
        for(int i = 0; i < cnt[1]; ++i)
        {
            dp[0] = (dp[0] << 1) % MOD;
        }
        // 枚举数字 i
        for(int i = 2, cur, times; i <= MAXV; ++i)
        {
            // 如果 i 不是质数，则 cur 等于 0
            // 如果 i 是质数，则 cur 表示 i 有哪些质数组成
            cur = own[i]; 
            // times 是数字 i 的出现次数
            times = cnt[i];
            if(cur != 0 && times != 0)
            {
                for(int status = LIMIT - 1; status >= 0; --status)
                {
                    if((status & cur) == cur)
                    {
                        dp[status] = (dp[status] + (long)dp[status ^ cur] * times) % MOD;
                    }
                }
            }
        }
        int ans = 0;
        // 要将 nums 中的数划分形成好子集 s 的状态
        for(int s = 1; s < LIMIT; ++s)
        {
            ans = (ans + dp[s]) % MOD;
        }
        return ans;
    }
};